\documentclass[a4paper,10pt]{report}
\usepackage[utf8]{inputenc}
\setlength{\parindent}{0mm} 
\usepackage{amsmath}
\usepackage{graphicx}
\usepackage{listings} \lstset{numbers=left, numberstyle=\tiny, numbersep=5pt} 
\lstset{language=C++} 
\title{Assignment 2 Solution}
\author{}

\begin{document}
\maketitle

\begin{tabular}{lll}
Jose Santiago Rodriguez & ptfs162  & santiagoropb@gmail.com\\
Akash Mittal & ptfs161 & akash.mittal@studium.fau.de\\
Bich Ngoc Vu & ptfs184 &  bich.ngoc.vu@studium.fau.de\\
\end{tabular}

\section*{Task 1}
\begin{figure}[h]
   \centering
   \includegraphics[width=\textwidth]{assignment3_11.png}
   \caption{Strided triad for $M \in \{1,2,4,8\}$}
   \label{figure1}
\end{figure}


A cache line consist of 64 bytes and therfore 8 double precision values. In Figure \ref{figure1}, the increase of $M$ is up to 8.
If the stride $M$ is smaller than the length of a cache line, consecutive cache
lines are still fetched from memory, and there's a reuse of the cache line.\\
The use of the transferred data volume can be expressed by $1/M$, thus the bandwidth and the performance will also drop to $1/M$. Here
prefetching is able to serve the load and store operations and hide the memory latency.

\newpage
Figure \ref{figure2} shows the performances for $M>8$.\\
\begin{figure}[h]
   \centering
   \includegraphics[width=\textwidth]{assignment3_12.png}
   \caption{Strided triad for $M \in \{1,2,3,\dots\}$}
   \label{figure2}
\end{figure}

If $M$ is larger than a cache line, the performance stays constant since only one item per cache line will be used and the reuse fraction is exactly zero.
Since prefetching plays a minor role, here the performance will drop and regulated by the memory latency.

\newpage
\section*{Task 2}
The first optimization is to allocate the two arrays on the heap, not on the stack, by using pointers.

\begin{lstlisting}[]{}
int N = 8192;
double **mat = new double*[N];
double **s = new double*[N];
for (int i = 0; i < N; ++i)
{
   mat[i] = new double[N];
   s[i] = new double[N];
}
\end{lstlisting}

For the next improvements a new variable is introduced, which holds the inverse value of $val$, so that the division has only to be executed once.
And also the way of accessing the array values must to be changed.
\begin{lstlisting}[]{}
val = (double)rand(); 
inv = 1./val;
for (int i = 0; i < N; ++i)
   {
   for (int j = 0; j < N; ++j)
   {
      mat[i][j] = inv * s[i][j];
   }
}
\end{lstlisting}
\end{document}          
